1. Field of the Invention
The present invention relates to Fast Fourier Transform on a computer system provided with a vector functional unit, and in particular relates to a Fast Fourier Transform system with reduced storing area for rotation factors used in Fast Fourier Transform.
2. Description of the Prior Art
Fast Fourier Transform processing on a computer system provided with a vector functional unit requires that a procedure consisting of input element rearrangement, vector addition, vector subtraction and rotation factor multiplication to be performed for three stages. In a conventional system, rotation factors to be vector loaded and used in each of the three stages are stored as they are in a rotation factor storing array as shown in FIG. 5.
Specifically, as shown in the flowchart of FIG. 6, rotation factors are read from the rotation factor storing array W as in FIG. 5 for every stage through vector loading.
When the rotation factors for all stages are stored in the storing array W as in FIG. 5, the area to store them needs to have a size as follows: EQU S=N/2.times.log N
where S is the size of the rotation factor storing area, N is the number of elements for Fast Fourier Transform, and log is a logarithm to the base two.
The size S of the storing area is generally larger than the size of input elements; when the number of elements for Fast Fourier Transform increases, the area to store the rotation factors becomes quite large. Besides, vector loading/storing must be performed the number of times represented by powers of 2 for rotation factor generation, which requires much time.
Thus, in a conventional Fast Fourier Transform system using a vector functional unit, rotation factors to be vector loaded and used for every stage of Fast Fourier Transform processing are stored as they are, which results in a large storing area. This causes a drawback of insufficient main storage memory capacity when there are many elements to be processed.